package chapter04_RecursionAndDynamic.minCoins;

/**
 * 描述：
 *      最少的找钱数
 *      给定一个arr数组，数组中的值代表货币面值的大小，给定一个aim，求找钱数为aim的用的最少的货币数，
 *      arr中都是正数，arr中的货币可以使用任意次
 * @author hl
 * @date 2021/6/4 10:13
 */
public class MinCoins {
    public static void main(String[] args) {
        int[] arr = {4,2,3};
        int aim = 30;
        MinCoins minCoins = new MinCoins();
        int num1 = minCoins.minCoins1(arr, aim);
        int num2 = minCoins.minCoins2(arr, aim);
        System.out.println(num1);
        System.out.println(num2);
    }


    /**
     * 构建一个N*(aim + 1)的二维数组dp，N是arr的下标，dp[i][j]表示使用arr中0~i的货币达到j面值的最小数量
     * dp[i][j]的位置可能来自两部分：
     *      1）不使用当前货币，不使用当前货币时的最小货币数dp[i - 1][j]
     *      2）使用当前货币，使用当前货币面值达到j - arr[i]面值的最小货币数量+1
     * @param arr
     * @param aim
     * @return
     */
    public int minCoins1(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return -1;
        }
        int[][] dp = new int[arr.length][aim + 1];
        for (int i = 1; i <= aim; i++) {
            dp[0][i] = Integer.MAX_VALUE;
            //赋值时必须要对dp[0][i - arr[0]]进行判断，判断是否能够找的开
            if (i >= arr[0] && dp[0][i - arr[0]] != Integer.MAX_VALUE) {
                dp[0][i] = dp[0][i - arr[0]] + 1;
            }
        }
        int left = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= aim; j++) {
                left = Integer.MAX_VALUE;
                if (j >= arr[i] && dp[i][j - arr[i]] != Integer.MAX_VALUE) {
                    left = dp[i][j - arr[i]] + 1;
                }
                dp[i][j] = Math.min(left, dp[i - 1][j]);
            }
        }
        return dp[arr.length - 1][aim] != Integer.MAX_VALUE ? dp[arr.length - 1][aim] : -1;
    }

    /**
     * 滚动数组空间优化，
     * 选择按行更新dp，而不是按列更新，是因为如果按列更新的话就依赖于位置(i, j - arr[i])，即往左arr[i]的位置，
     * 最差的情况需要准备a（arr[i]的最大值）个一维数组假，
     * 如果按列更新的话，依赖于(i - 1, j)的位置，此情况下只需要准备一个一维数组即可
     * @param arr
     * @param aim
     * @return
     */
    public int minCoins2(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return -1;
        }
        int[] dp = new int[aim + 1];
        int max = Integer.MAX_VALUE;
        for (int j = 1; j <= aim; j++) {
            dp[j] = max;
            //dp[j - arr[0]] == max说明j - arr[0]位置无法找开
            if (j >= arr[0] && dp[j - arr[0]] != max) {
                dp[j] = dp[j - arr[0]] + 1;
            }
        }
        int left = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= aim; j++) {
                left = max;
                if (j >= arr[i] && dp[j - arr[i]] != max) {
                    left = dp[j - arr[i]] + 1;
                }
                dp[j] = Math.min(left, dp[j]);
            }
        }
        return dp[aim] != max ? dp[aim] : -1;
    }
}
